Various mechanisms exist for accessing and modifying priority queues. Priority queues are a modified queue construct. In a first-in-first-out queue (FIFO), for instance, the first element to be placed on the queue (enqueued or pushed) is the first to be removed (dequeued or popped). In a priority queue, the first element to be removed (popped) is the element in the queue with the highest priority at the time. Thus, the priority queue may have an underlying representation that favors the ordered dequeuing of elements based on a user-defined priority on those elements.
Priority queues are often used for storage of information or tasks in multi-threaded computing systems. However, in a multi-threaded system, more than one thread may try to access the queue at the same time. Thus, existing systems may implement a series of locking algorithms to ensure that there is no contention for adding and removing items, and to maintain the underlying representation of the priority queue. The priority queue is often maintained with a heap data structure, for ease of locating the highest priority element and restructuring after additions to and removals from the heap.
Many algorithms for implementing concurrent priority queues are based on mutual exclusion (locking). However, mutual exclusion algorithms cause blocking, which may degrade overall performance of the system. Further, thread locking typically allows only one thread to operate at a time, which reduces this method to that of serial performance with the addition of locking overhead. In some cases, the overhead of this method may lead to worse than serial performance. Another type of solution is that some algorithms may attempt to perform concurrently within the queue itself. In this case, multiple threads are operating on the queue at the same time, so access to each element of the queue must protected. This may use an internal locking or other system to prevent races on specific queue elements. Such algorithms improve concurrency, but many such algorithms were too complex and suffered high overhead from the internal locking, and so did not perform well in practice.